package Exams.FeiBu;

import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class q1 {
    /*
    会员题 1057 校园自行车分配
    直接通过优先队列的方式解决
    用一个set记录已经用过的bike
     */
    public int[] assignBikes(int[][] workers, int[][] bikes) {
        PriorityQueue<int[]> pq =
                new PriorityQueue<>(
                        (a, b) -> { // 距离， 工人， 自行车
                            if (a[0] != b[0]) return a[0] - b[0];
                            if (a[1] != b[1]) return a[1] - b[1];
                            return a[2] - b[2];
                        });
        for (int i = 0; i < workers.length; i++) {
            for (int j = 0; j < bikes.length; j++) {
                int manhattan =
                        Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1]);
                pq.offer(new int[]{manhattan, i, j});
            }
        }
        int[] res = new int[workers.length];
        Arrays.fill(res, -1);
        Set<Integer> used = new HashSet<>(); // used bikes
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            if (used.contains(cur[2]) || res[cur[1]] != -1) continue;
            res[cur[1]] = cur[2];
            used.add(cur[2]);
        }
        return res;
    }

}
